def insertion_sort(arr):
    arr = arr.copy()
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

def bubble_sort(arr):
    arr = arr.copy()
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break
    return arr

def quick_sort(arr):
    """
    快速排序算法的改进版本，使用三数取中法选择基准元素（pivot），
    以避免在已排序或逆序数据上的递归深度过大问题。

    Args:
        arr: 需要排序的列表。

    Returns:
        排序后的新列表。
    """
    # 创建一个副本，避免修改原始列表
    arr = arr.copy()

    def _quick_sort(a, l, r):
        """
        递归进行快速排序。

        Args:
            a: 当前需要排序的子列表。
            l: 子列表的起始索引。
            r: 子列表的结束索引。
        """
        # 基本情况：如果子列表只有一个或零个元素，则已经有序
        if l < r:
            # 执行划分操作，获取基准元素的最终位置
            # partition 函数现在会使用三数取中法选择基准
            pi = partition(a, l, r)
            # 递归排序基准元素左边的子列表
            _quick_sort(a, l, pi - 1)
            # 递归排序基准元素右边的子列表
            _quick_sort(a, pi + 1, r)

    def partition(a, l, r):
        """
        对子列表进行划分操作，并将基准元素放到正确的位置。
        使用三数取中法选择基准（median-of-three）。

        Args:
            a: 当前需要划分的子列表。
            l: 子列表的起始索引。
            r: 子列表的结束索引。

        Returns:
            基准元素的最终位置索引。
        """
        # --- 三数取中法选择基准 ---
        # 找到中间元素的索引
        mid = l + (r - l) // 2

        # 排序 a[l], a[mid], a[r] 这三个元素，确保它们是 l <= mid <= r
        # 这样，a[mid] 就是这三个数的中位数
        # 比较 a[l] 和 a[mid]
        if a[l] > a[mid]:
            a[l], a[mid] = a[mid], a[l]
        # 比较 a[l] 和 a[r]
        if a[l] > a[r]:
            a[l], a[r] = a[r], a[l]
        # 比较 a[mid] 和 a[r]
        if a[mid] > a[r]:
            a[mid], a[r] = a[r], a[mid]

        # 现在，a[mid] 是这三个数的中位数。
        # 将中位数（a[mid]）与最后一个元素（a[r]）交换。
        # 这样，我们将中位数作为基准，并将其放在了子列表的末尾，
        # 方便使用标准的 Lomuto 划分方法。
        a[mid], a[r] = a[r], a[mid]

        # 现在，基准元素是 a[r] (原始的中位数)
        pivot = a[r]

        # --- 标准 Lomuto 划分过程 ---
        # i 指向小于等于基准的区域的最后一个元素
        i = l - 1

        # 遍历从 l 到 r-1 的所有元素 (不包含基准元素 a[r])
        for j in range(l, r):
            # 如果当前元素小于或等于基准
            if a[j] <= pivot:
                # 移动 i 指针
                i += 1
                # 交换 a[i] 和 a[j]，将小于等于基准的元素放到前面
                a[i], a[j] = a[j], a[i]

        # 将基准元素 (a[r]) 放到正确的位置 (i+1)
        # 此时，i 指向小于等于基准区域的最后一个元素，
        # 所以基准应该放在 i+1 的位置
        a[i + 1], a[r] = a[r], a[i + 1]

        # 返回基准元素的最终位置
        return i + 1

    # 调用内部的快速排序函数对整个列表进行排序
    _quick_sort(arr, 0, len(arr) - 1)

    # 返回排序后的列表副本
    return arr

def heap_sort(arr):
    arr = arr.copy()
    def heapify(a, n, i):
        largest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and a[l] > a[largest]:
            largest = l
        if r < n and a[r] > a[largest]:
            largest = r
        if largest != i:
            a[i], a[largest] = a[largest], a[i]
            heapify(a, n, largest)
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

def merge_sort(arr):
    arr = arr.copy()
    def _merge_sort(a):
        if len(a) <= 1:
            return a
        mid = len(a) // 2
        left = _merge_sort(a[:mid])
        right = _merge_sort(a[mid:])
        return merge(left, right)
    def merge(left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    return _merge_sort(arr)

def shell_sort(arr):
    arr = arr.copy()
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

class SortingAlgorithms:
    def __init__(self):
        self.bubble_sort = bubble_sort
        self.insertion_sort = insertion_sort
        self.quick_sort = quick_sort
        self.heap_sort = heap_sort
        self.merge_sort = merge_sort
        self.shell_sort = shell_sort
